|
"The Complexity of Songs" was a journal article published by computer scientist Donald Knuth in 1977,〔 as an in-joke about computational complexity theory. The article capitalizes on the tendency of popular songs to devolve from long and content-rich ballads to highly repetitive texts with little or no meaningful content.〔Steven Krantz (2005) "Mathematical Apocrypha Redux", ISBN 0-88385-554-2, pp.2, 3.〕 The article notes how some songs can reach a complexity level, for a song of length ''N'' words, as formula: . The gist of the article is repeated below, maintaining the wit of the key concepts. ==Article summary== Knuth writes that "our ancient ancestors invented the concept of refrain" to reduce the space complexity of songs, which becomes crucial when a large number of songs is to be committed to one's memory. Knuth's Lemma 1 states that if ''N'' is the length of a song, then the refrain decreases the song complexity to ''cN'', where the factor ''c'' < 1.〔 Reprinted in: 〕 Knuth further demonstrates a way of producing songs with O() complexity, an approach "further improved by a Scottish farmer named O. MacDonald".〔 More ingenious approaches yield songs of complexity O(), a class known as "''m'' bottles of beer on the wall". Finally, the progress during the 20th century — stimulated by the fact that "the advent of modern drugs has led to demands for still less memory" — leads to the ultimate improvement: Arbitrarily long songs with space complexity O(1), e.g. for a song to be defined by the recurrence relation〔 : : 'That's the way,' 'I like it,' , for all : 'uh huh,' 'uh huh' 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「The Complexity of Songs」の詳細全文を読む スポンサード リンク
|